from tree import binary_tree,ubb_tree
from stack import SinglyLinkedStack
from queue import SinglyLinkedQueue
'''
Exercise 10.4-2:print all tree nodes of a given binary tree
'''
def print_tree_node(root):
    if root == None:
        return
    print root.value
    print_tree_node(root.left)
    print_tree_node(root.right)

'''
Exercise 10.4-3:iterative version of printing all tree nodes of a given binary tree
'''
def print_tree_node_iterative(root):
    stack = SinglyLinkedStack()
    while True:
        if root == None:
            return
        print root.value
        if root.left !=None:
            stack.push(root.left)
        if root.right !=None:
            stack.push(root.right)
        
        root = stack.pop()
'''
Exercise 10.4-4
'''    
def print_ubb_tree_node(root):
    if root == None:
        return
    print root.value
    print_ubb_tree_node(root.left)
    print_ubb_tree_node(root.right_sibling)

'''
Exercise 10.4-5
'''
def print_tree_node_BFS(root):
    temp_queue = SinglyLinkedQueue()
    while True:
        if root == None:#Termination 
            return
        if root.left !=None:
            temp_queue.enqueue(root.left)
        if root.right!=None:
            temp_queue.enqueue(root.right)
        print root.value
        root = temp_queue.dequeue()
'''Main Entry'''

#initialization
'''
        1(root)
      /  \
    2     3
   /\    /\
  4 6   5 7
 /
8
'''
b_tree = binary_tree()
b_tree.random_insert(1)
b_tree.random_insert(2)
b_tree.random_insert(3)
b_tree.random_insert(4)
b_tree.random_insert(5)
b_tree.random_insert(6)
b_tree.random_insert(7)
b_tree.random_insert(8)
#test begin
#print_tree_node(b_tree.root)
#print_tree_node_iterative(b_tree.root)
print_tree_node_BFS(b_tree.root)
 
'''
        1(root)
      /  
    2--- 3---4---5
   /    /       /
  6    7---8   9
'''
u_tree = ubb_tree(1)
u_tree.insertAsChild(1, 2)
u_tree.insertAsChild(1, 3)
u_tree.insertAsChild(1, 4)
u_tree.insertAsChild(1, 5)
u_tree.insertAsChild(2, 6)
u_tree.insertAsChild(3, 7)
u_tree.insertAsChild(3, 8)
u_tree.insertAsChild(5, 9)

#test begin
#print_ubb_tree_node(u_tree.getNode("ROOT"))

